package com.dmall.graph.floodfill;

/**
 * 解题思路：使用DFS查找组件中的每个正方形。然后，对于每个正方形，如果它有一个在网格之外的邻居（有一个网格之外的邻居表示当前正方形处在边界位置）或不同的颜色，则将其上色。
 */
public class Leetcode1034 {

    private int R, C;
    private int[][] grid;
    private int[][] visited;
    private int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    private int color;

    public int[][] colorBorder(int[][] grid, int r0, int c0, int color) {
        this.grid = grid;
        R = grid.length;
        C = grid[0].length;
        visited = new int[R][C];
        this.color = grid[r0][c0];
        dfs(r0, c0);
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (visited[i][j] == 2) {
                    this.grid[i][j] = color;
                }
            }
        }

        return this.grid;
    }

    private void dfs(int x, int y) {
        if (visited[x][y] == 0) {
            visited[x][y] = 1;
        }
        for (int i = 0; i < dirs.length; i++) {
            int nextx = x + dirs[i][0];
            int nexty = y + dirs[i][1];
            if (inArea(nextx, nexty) && visited[nextx][nexty] == 0 && grid[nextx][nexty] == this.color) {
                visited[nextx][nexty] = 1;
                if (nextx == 0 || nextx == R - 1 || nexty == 0 || nexty == C - 1) {
                    visited[nextx][nexty] = 2;
                }
                if (visited[nextx][nexty] != 2) {
                    for (int j = 0; j < dirs.length; j++) {
                        int dirx = nextx + dirs[j][0];
                        int diry = nexty + dirs[j][1];
                        if (inArea(dirx, diry) && grid[dirx][diry] != grid[nextx][nexty]) {
                            visited[nextx][nexty] = 2;
                            break;
                        }
                    }
                }
                dfs(nextx, nexty);
            }
        }

        if (visited[x][y] == 1) {
            if (x == 0 || x == R - 1 || y == 0 || y == C - 1) {
                visited[x][y] = 2;
            }
            if (visited[x][y] != 2) {
                for (int j = 0; j < dirs.length; j++) {
                    int dirx = x + dirs[j][0];
                    int diry = y + dirs[j][1];
                    if (inArea(dirx, diry) && grid[dirx][diry] != grid[x][y]) {
                        visited[x][y] = 2;
                        break;
                    }
                }
            }
        }
    }

    private boolean inArea(int x, int y) {
        return x >= 0 && x < R && y >= 0 && y < C;
    }

    public static void main(String[] args) {
        int[][] grid = {{1, 1, 1}, {1, 1, 1}, {1, 1, 1}};
        Leetcode1034 leetcode1034 = new Leetcode1034();
        int[][] result = leetcode1034.colorBorder(grid, 0, 0, 2);
        for (int i = 0; i < result.length; i++) {
            for (int j = 0; j < result[i].length; j++) {
                System.out.print(result[i][j] + " ");
            }
            System.out.println();
        }
    }
}
